package com.jack.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by zhang_j on 2020/6/30
 * 采用分治法的一个非常典型的应用。
 */
public class mergesort {

    public static void main(String[] args) {
        int[] nums = {9, 7, 8, 6, 5, 3, 3, 2, 10};
        int[] result = mergesort2(nums);
        for(int i : result){
            System.out.print(i+",");
        }
    }

    private static int[] mergesort2(int[] nums){
        if(nums == null){
            return null;
        }
        int n = nums.length;
        if(n == 1){
            return nums;
        }
        return merge2(mergesort2(Arrays.copyOfRange(nums, 0, (n+1)/2)), mergesort2(Arrays.copyOfRange(nums, (n+1)/2, n)));
    }

    private static int[] merge2(int[] left, int[] right){
        int m = left.length;
        int n = right.length;
        int[] result = new int[m+n];
        int i = 0, j = 0, index = 0;
        while(i < m && j < n){
            if(left[i] < right[j]){
                result[index++] = left[i++];
            }else{
                result[index++] = right[j++];
            }
        }
        while(i < m){
            result[index++] = left[i++];
        }
        while(j < n){
            result[index++] = right[j++];
        }
        return result;
    }













    private static int[] mergesort1(int[] nums) {
        if (nums == null) {
            return null;
        }
        int n = nums.length;
        int pow = 2;
        while (pow < n) {
            int gap = pow / 2;
            for (int i = 0; i + gap < n; i += pow) {
                if (nums[i] > nums[i + gap]) {
                    int tmp = nums[i];
                    nums[i] = nums[i + gap];
                    nums[i + gap] = tmp;
                }
            }
            pow *= 2;
        }
        return nums;
    }


    private static int[] mergesort(int[] nums) {
        if (nums == null) {
            return nums;
        }
        int n = nums.length;
        if (n < 2) {
            return nums;
        }
        int[] left = Arrays.copyOfRange(nums, 0, (n + 1) / 2);
        int[] right = Arrays.copyOfRange(nums, (n + 1) / 2, n);
        return merge(mergesort(left), mergesort(right));
    }

    private static int[] merge(int[] left, int[] right) {
        List<Integer> list = new ArrayList<>();
        int m = left.length;
        int n = right.length;
        int i = 0, j = 0;
        while (i < m && j < n) {
            list.add(left[i] < right[j] ? left[i++] : right[j++]);
        }
        while (i < m) {
            list.add(left[i++]);
        }
        while (j < n) {
            list.add(right[j++]);
        }
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }
}
